from BuildTree import *


class Solution:

    def lowestCommonAncestor(self, root: TreeNode, p: int, q: int) -> TreeNode:
        def poOrder(node: TreeNode):
            if not node: return None
            left = poOrder(node.left)
            right = poOrder(node.right)
            if isinstance(left, TreeNode):
                return left
            if isinstance(right, TreeNode):
                return right
            if node.val == p:
                return 'p'
            if node.val == q:
                return 'q'
            if left == 'p' and right == 'q' or left == 'q' and right == 'p':
                return node
            if not right:
                return left
            if not left:
                return right
            return None

        return poOrder(root)


if __name__ == '__main__':
    s = Solution()
    null = None
    root = build_tree_from_level_order([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
    r = s.lowestCommonAncestor(root, 7, 6).val
    print(r)
